package day04;

import java.util.*;

/**
 * @author ZJX
 * @version 1.0
 * @descption 哈希表
 * @since 2025/10/12 20:22
 */
public class O {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>(); // k为数字 v为索引下标
        for (int i = 0; i < nums.length; i++) {
            int n = target - nums[i];
            if (map.containsKey(n)) {
                return new int[]{i, map.get(n)};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int l = i + 1, r = nums.length - 1;
            while (r > l) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    ret.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (r > l && nums[l] == nums[l + 1]) l++;
                    while (r > l && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                } else if (sum > 0) {
                    r--;
                } else {
                    l++;
                }
            }
        }
        return ret;
    }

    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int n = nums.length / 2;
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
            if (map.get(num) > n) {
                return num;
            }
        }
        return -1;
    }

    public int longestConsecutive(int[] nums) {
        int n = nums.length;
        if (n == 0 || n == 1) {
            return n;
        }
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int ret = 1;
        for (int num : set) {
            if (!set.contains(num - 1)) {
                int curNum = num;
                int curLen = 1;
                while (set.contains(curNum + 1)) {
                    curNum++;
                    curLen++;
                }
                ret = Math.max(ret, curLen);
            }
        }
        return ret;
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int sLen = s.length();
        int pLen = p.length();
        if (sLen < pLen) return ret; // 长度不够无法匹配

        HashMap<Character, Integer> sMap = new HashMap<>();
        HashMap<Character, Integer> pMap = new HashMap<>();
//        填充pMap
        for (int i = 0; i < pLen; i++) {
            char c = p.charAt(i);
            pMap.put(c, pMap.getOrDefault(c, 0) + 1);
        }
        for (int i = 0; i < pLen; i++) {
            char c = s.charAt(i);
            sMap.put(c, sMap.getOrDefault(c, 0) + 1);
        }
        if (sMap.equals(pMap)) {
            ret.add(0);
        }

        // 4. 滑动窗口：从pLen开始遍历s
        for (int i = pLen; i < sLen; i++) {
            char leftChar = s.charAt(i - pLen);
            sMap.put(leftChar, sMap.get(leftChar) - 1);
            if (sMap.get(leftChar) == 0) {
                sMap.remove(leftChar);
            }
            char rightChar = s.charAt(i);
            sMap.put(rightChar, sMap.getOrDefault(rightChar, 0) + 1);
            if (sMap.equals(pMap)) {
                ret.add(i - pLen + 1);
            }
        }
        return ret;
    }
}

